//#include<stdio.h>
//void InsertSort(int* a, int n)
//{
//	/*int cur = 1;
//	int i = 1;
//	while (i < n)
//	{
//		cur = i;
//		int tmp = a[cur];
//		while (cur - 1 >= 0 && tmp < a[cur - 1])
//		{
//			a[cur] = a[cur - 1];
//			cur--;
//		}
//		a[cur] = tmp;
//		i++;
//	}*/
//	int i = 0;
//	for (i = 0; i < n-1; i++)
//	{
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//			}
//			else
//			{
//				break;
//			}
//			end--;
//		}
//		a[end + 1] = tmp;
//	}
//}
//void test1()
//{
//	int arr[] = { 2,6,1,3,9,5,4,1,7 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int i = 0;
//	for (i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	InsertSort(arr, sz);
//	printf("\n");
//	for (i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//}
//int main()
//{
//	test1();
//	return 0;
//}
#include<stdbool.h>
#include<stdio.h>
//Definition for a binary tree node.
struct TreeNode 
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
bool isUnivalTree(struct TreeNode* root) 
{
	if (root == NULL)
		return true;
	if (root->left != NULL && root->right != NULL)
		return isUnivalTree(root->left) && isUnivalTree(root->right) && root->val == root->left->val && root->val == root->right->val;
	if(root->left==NULL&&root->right!=NULL)
		return isUnivalTree(root->right) &&  root->val == root->right->val;
	if (root->left != NULL && root->right == NULL)
		return isUnivalTree(root->left) && root->val == root->left->val;
	return true;
}
int maxDepth(struct TreeNode* root) 
{
	if (root == NULL)
		return 0;
	int leftHigh = maxDepth(root->left);
	int rightHigh = maxDepth(root->right);
	return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}
struct TreeNode* invertTree(struct TreeNode* root) 
{
	if (root == NULL)
		return NULL;
	struct TreeNode* tmp = root->left;
	root->left = invertTree(root->right);
	root->right = invertTree(tmp);
	return root;
}
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
	if (p == NULL && q == NULL)
		return true;
	if (q != NULL && p != NULL)
		return isSameTree(p->left, q->left) && isSameTree(p->right, q->right) && p->val == q->val;
	return false;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{
	if (root == NULL)
		return false;
	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot) || isSameTree(root->left, subRoot) || isSameTree(root->right, subRoot) || isSameTree(root, subRoot);
}


#include"Sort.h"
void test1()
{
	int arr[] = { 9,6,4,8,3,2,1,6,7,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	InsertSort(arr, sz);
	printf("\n");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	test1();
	return 0;
}

